package hashTable;

import java.util.*;
//哈希表就是用空间换时间的方法，它查询一个数据耗时O(1)

public class hashTableTest1 {
    /**
     * 242.判断两个字符串是否是异位词 -easy
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) {
            return false;
        }
        int[] count = new int[26]; //英文该题目限制了只有26个字母，所以用数组来统计每个字母出现的次数-避免空间浪费
        //而且用hashSet,set把数值映射到key上都要做hash计算的
        for(int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++; //统计s字符串中每个字符出现的次数
        }
        for(int i = 0; i < t.length(); i++) {
            count[t.charAt(i) - 'a']--; //减去t字符串中每个字符出现的次数
        }
        for(int i = 0; i < count.length; i++) {
            if(count[i] != 0) {
                return false; //如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符
            }
        }
        return true;
    }

    /**
     * 349.两个数组的交集 -easy
     * @param nums1
     * @param nums2
     * @return
     */

    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            //返回空数组
            return new int[0];
        }
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums1.length; i++) {
            set.add(nums1[i]);
        }
        Set<Integer> res = new HashSet<>();
        for(int i = 0; i < nums2.length; i++) {
            if(set.contains(nums2[i])) {
                res.add(nums2[i]);
            }
        }
        int[] arrResult = res.stream().mapToInt(Integer::intValue).toArray();
        return arrResult;
    }

    /**
     * 350 两个数组的交集 II -easy
     * @param nums1
     * @param nums2
     * @return
     */

    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length) {
            //确保nums1是短的
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums1.length; i++) {
            int count = map.getOrDefault(nums1[i], 0);
            map.put(nums1[i], count + 1);
        }
        int[] res = new int[nums1.length];
        int index = 0;
        for(int i = 0; i < nums2.length; i++) {
            int count = map.getOrDefault(nums2[i], 0);
            if(count > 0) {
                res[index++] = nums2[i];
                map.put(nums2[i], count - 1);
            } else {
                map.remove(nums2[i]);
            }
        }
        return Arrays.copyOfRange(res, 0, index);

    }


    /**
     * 202.快乐数 -easy
     * @param n
     * @return
     * 快乐数的定义是基于一个计算过程，即对一个正整数，不断将其替换为它各个位上数字的平方和，
     * 如果最终这个过程能够收敛到1，
     * 则这个数被称为快乐数。相反，如果在这个过程中形成了一个不包含1的循环，则该数不是快乐数
     */
    public boolean isHappy(int n) {
        //sumSet用来存储每个数字的平方和，如果sumSet中存在1就是快乐数
        //如果循环过程(不断平方和)中,sum结果有重复，则一定不是快乐数，返回false
        Set<Integer> sumSet = new HashSet<>();
        while(n!= 1) {
            //获取n的平方和
            if(sumSet.contains(n)) {
                return false;
            } else {
                sumSet.add(n);
                n = bitSquareSum(n);
            }
        }
        return true;

    }

    public boolean isHappy1(int n) {
        //根据求解过程，参考142. 环形链表 II -medium是否是环形链表的解法
        //快慢指针，快指针每次走两步，慢指针每次走一步，如果快慢指针相遇，就是有环，
        //如果循环点不是1，则不是快乐数
        int slow = n, fast = n;
        do{
            slow = bitSquareSum(slow);
            fast = bitSquareSum(fast);
            fast = bitSquareSum(fast);
        }while(slow != fast);

        return slow == 1;

    }
    public int bitSquareSum(int n) {
        int sum = 0;
        while(n != 0) {
            int temp = n % 10;
            sum += temp * temp;
            n = n / 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(1/10);

    }
}
